class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (height.size() == 0) {
            return 0;
        }
        int n = height.size();
        vector<int> left(n);
        vector<int> right(n);
        stack<int> stk;

        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && height[stk.top()] >= height[i]) {
                stk.pop();
            }
            if (stk.empty()) {
                left[i] = 0;
            } else {
                left[i] = stk.top() + 1;
            }
            stk.push(i);
        }

        while (!stk.empty()) {
            stk.pop();
        }

        for (int i = n - 1; i >= 0; --i) {
            while (!stk.empty() && height[stk.top()] >= height[i]) {
                stk.pop();
            }
            if (stk.empty()) {
                right[i] = n - 1;
            } else {
                right[i] = stk.top() - 1;
            }
            stk.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, height[i] * (right[i] - left[i] + 1));
        }
        return ans;
    }
};
